#include <bits/stdc++.h>
using namespace std;

int n, t, f21[1000001], f1[1000001], f0[1000001];
string s, p;

string f(int i) {
	if (i == 1) return "0";
	if (i == 2) return "1";
	return f(i - 1) + f(i - 2);
}

int main() {
	freopen("brotherhood.in", "r", stdin);
	freopen("brotherhood.out", "w", stdout);
	scanf("%d%d", &n, &t);
	if (n >= 1000000) {
		puts("QAQ");
		return 114514;
	}
	f21[5] = f21[6] = 1;
	f1[1] = 0;
	f1[2] = 1;
	f0[1] = f0[3] = 1;
	if (n <= 15 && 0) {
		s = f(n);
		int sz = s.size();
		while (t--) {
			cin >> p;
			int szp = p.size(), tot = 0;
			for (int i = 0; i + szp - 1  < sz; ++i) {
				if (s.substr(i, szp) == p) ++tot;
			}
			printf("%d\n", tot);
		}
	} else {
		const int P = 1e9 + 7;
		for (int i = 7; i <= n; ++i) {
			f21[i] = 1ll * f21[i - 1] + f21[i - 2] + (i & 1);
			f21[i] %= P;
		}
		for (int i = 3; i <= n; ++i) {
			f0[i] = (1ll * f0[i - 1] + f0[i - 2]) % P;
			f1[i] = (1ll * f1[i - 1] + f1[i - 2]) % P;
		}
		while (t--) {
			cin >> p;
			if (p.size() > 2) {
				puts("0");
			} else {
				if (p.size() == 1) {
					if (p[0] == '1') {
						printf("%d\n", f1[n]);
					} else {
						printf("%d\n", f0[n]);
					}
				} else {
					if (p[0] == '1') printf("%d\n", f21[n]);
					else puts("0");
				}
			}
		}
	}
	return 0;
}
